1. Field of the Invention
The invention relates to cryptography, particularly a word-oriented technique for generating a pseudo-random sequence, such as a keystream for use in, e.g., a stream cipher. Advantageously, this technique is not only fast and secure but also requires relatively little processing power to implement, i.e., is xe2x80x9clightweightxe2x80x9d.
2. Description of the Prior Art
Over the centuries, for as long as information has been communicated between two individuals, the information has been susceptible to third-party interception, eavesdropping, compromise and/or corruption. Clearly, the problem of securely protecting information from such acts has existed for quite a long time.
Traditionally, this problem has been handled through the development, over the years, of increasingly sophisticated cryptographic techniques. One class of these techniques involves key-based ciphers. Through a key-based cipher, sequences of intelligible data, i.e., plaintext, that collectively form a message are each mathematically transformed, through an enciphering algorithm, into seemingly unintelligible data, i.e., so-called ciphertext. Not only must the transformation be completely reversible, i.e., two way in the sense that the ciphertext must be invertable back to its corresponding original plaintext but also on a 1:1 basis, i.e., each element of plaintext can only be transformed into one and only one element of ciphertext. In addition, a particular cipher that generated any given ciphertext must be sufficiently secure from cryptanalysis. To provide a requisite level of security, a unique key is selected which defines only one unique corresponding cipher, i.e., precluding, to the extent possible, a situation where multiple differing keys each yields reversible transformations between the same plaintext-ciphertext correspondence. The strength of any cryptographic technique and hence the degree of protection it affords from third-party intrusion is directly proportional to the time required, by a third-party, to perform cryptanalysis, e.g., with a key-based cipher to successfully convert the ciphertext into its corresponding plaintext without prior knowledge of the key. While no encryption technique is completely impervious from cryptanalysis, an immense number of calculations and an extremely long time interval required thereforxe2x80x94given the computing technology then availablexe2x80x94required to break a cipher without prior knowledge of its key effectively renders many techniques, for all practical intents and purposes, sufficiently secure to warrant their widespread adoption and use.
Key-based ciphers include both symmetric and public-key algorithms. Inasmuch as public-key algorithms are not relevant to the present invention, they will not be discussed any further.
Symmetric algorithms are those through which the encryption key can be calculated from the decryption key, and vice versa. Generally, in these algorithms, the two keys are the same, with the security of the algorithm resting, in good measure, on the security of the key. Symmetric algorithms themselves are divided into stream ciphers (also referred to as xe2x80x9cstream algorithmsxe2x80x9d) and block ciphers. A stream cipher operates on a bit or byte of plaintext at a time, in contrast to block ciphers which operates on a predefined group of bits (a xe2x80x9cblockxe2x80x9d, such as 64 bits) of plaintext at a time. Since block ciphers are also not relevant to the present invention, they will also not be discussed any further.
A very simple form of a stream cipher relies on generating, at an encryption end and through a so-called keystream generator, a pseudo-random sequence (K) of bits k1, k2, k3, . . . , kn. These bits are combined, on a bit-by-bit exclusive-OR (XOR) basis, with incoming bits of plaintext (P), specifically p1, p2, p3, . . . , pn to yield resulting bits (C), specifically c1, c2, c3, . . . , cn, of ciphertext. At a decryption end, the bits of ciphertext are combined, again on a bit-by-bit XOR basis, with an identical keystream to recover the plaintext bits. With this cipher, the security of the cipher itself, apart from that of the key itself, rests entirely on the keystream, i.e., the level of difficulty which a cryptanalyst encounters in attempting to discern, from the ciphertext, the algorithm that generates the pseudo-random keystream. With a stream cipher, both the encrypting and decrypting ends of a communications link use identical keystream generators that are initialized in the same manner and operate in synchronization with respect to the ciphertext. Identical keystreams assure, in the absence of transmission and other errors, that the recovered plaintext will match the incoming plaintext. For further details on stream ciphers, the reader is referred to B. Schneier, Applied Cryptographyxe2x80x94Second Edition ((copyright) 1996, John Wiley and Sons) pages 197-199 and 397-398; and G. Simmons, Contemporary Cryptography ((copyright)1992, IEEE Press), pages 67-75xe2x80x94which are all incorporated by reference herein.
As recently as a few years ago, if a cipher was of such complexity that it required on the order of man-years or more to break, in view of the state of the processing technology then available to do so, the underlying cryptographic technique was viewed by many as rendering a sufficient degree of security to warrant its use. However, computing technology continues to rapidly evolve. Processors, once unheard of just a few years ago in terms of their high levels of sophistication and speed, are becoming commercially available at ever decreasing prices. Consequently, processing systems, such as personal computers and workstations, that were previously viewed as not possessing sufficient processing power to break many so-called xe2x80x9csecurexe2x80x9d cryptographic ciphers are now, given their current power and sophistication, providing third parties with the necessary capability to effectively break those same ciphers. What may have taken years of continual computing a decade ago can now be accomplished in a very small fraction of that time. Hence, as technology evolves, the art of cryptography advances in lockstep in a continual effort to develop increasingly sophisticated cryptographic techniques that withstand correspondingly intensifying cryptanalysis.
Over the past few years, the Internet community has experienced explosive and exponential growthxe2x80x94growth that, by many accounts, will only continue increasing. Given the vast and increasing magnitude of this community, both in terms of the number of individual users and web sites and sharply reduced costs associated with electronically communicating information, such as e-mail messages and electronic files, over the Internet between one user and another as well as between any individual client computer and a web server, electronic communication, rather than more traditional postal mail, is rapidly becoming a medium of choice for communicating information, whether it be, e.g., an e-mail message or a program update file. In that regard, the cost of sending an electronic file between computers located on opposite sides of the Earth is a very small fraction of the cost associated with storing that file on a diskette (or other media) and transporting that media between these locations even through the least expensive class of postal mail service. However, the Internet, being a publicly accessible network, is not secure and, in fact, has been and increasingly continues to be a target of a wide variety of attacks from various individuals and organizations intent on eavesdropping, intercepting and/or otherwise compromising or even corrupting message traffic flowing on the Internet or illicitly penetrating sites connected to the Internet. This security threat, in view of the increasing reliance placed on use of the Internet as a preferred medium of communication, exacerbates the efforts in the art, otherwise fostered by primarily continuing advances in computing power, to develop increasingly strong cryptographic techniques that provide enhanced levels of security to electronic communication.
Stream ciphers, given their nature of generating extended pseudo-random sequences, would be particularly useful in encrypting extremely long plaintext streams, such as video, or packet traffic, such as TCP/IP packets, appearing on, e.g., a Internet connection.
Currently, a conventional stream cipher that encounters rather widespread use is an xe2x80x9cRC4xe2x80x9d stream cipher (xe2x80x9cRC4xe2x80x9d is a registered trademark of RSA Data Security Inc. of Redwood City, Calif.). Advantageously, the RC4 stream cipher is independent of the plaintext being encrypted and is quite easy to implement. This cipher is claimed in the art to be immune to differential and linear cryptanalysis and is highly non-linear with approximately 21700 different states. This cipher relies on a 256-value substitution box, a so-called xe2x80x9cS-boxxe2x80x9d, to generate each byte of an output keystream. This S-box initially contains entries which are permutations, as a function of a variable length key, of values 0 through 255. In use, the contents of the S-box slowly evolve with use in a fashion that ensures that every element in the box randomly changes; hence, supporting a belief in the art that the output byte is a secure pseudo-random sequence. The RC4 cipher is byte-based and generates an output byte that is XORed with either a byte of plaintext to produce a corresponding byte of ciphertext, or with a byte of ciphertext to produce a corresponding byte of recovered plaintext.
Presently, the RC4 cipher appears to be sufficiently secure to thwart realistic cryptanalysis and, given its ease of implementation, quite useful in a broad range of applications. However, in some applications, such as real-time encryption of multi-stream video data, such as in a video server, as well as keyboard entries at a local client computer, this cipher has proven to be too slow to be effective. Moreover and currently, TCP/IP layer encryptionxe2x80x94which would, if implemented through a stream cipher, be rather advantageousxe2x80x94can not be effectively provided in real-time in certain high-data rate applications, such as video streaming, due to excessive processing time required to generate the keystream.
Furthermore, a multitude of consumer and other low-end products, such as, e.g., remote controls, home devices and personal digital assistants, are currently incorporating microprocessors, though with rather limited processing capacity (e.g., diminished execution speed). To provide sufficient security for their users, these devices should implement some form of encrypted communication. Unfortunately, the limited computing power currently available in such devices, effectively precludes use of the RC4 cipher, or other conventional keystream generators, in such devices and hence, to a certain extent, frustrates the ability of these devices to support sufficiently secure encrypted communication. This result, is particularly evident with respect to the RC4 stream cipher given its byte-based nature and hence relatively slow throughput.
Therefore, a need exists in the art for a cryptographic technique for generating a pseudo-random keystream for use in, e.g., a stream cipher, that is considerably faster than conventional algorithms, such as the RC4 cipher, and provides at least the same, if not a greater, level of security as does these algorithms. Such a technique would advantageously find use in a multitude of applications which, owing to, e.g., high data rates or limited available processing resources, are simply not amenable to use of the RC4 cipher or other conventional keystream generators.
Advantageously, our inventive technique for generating a pseudo-random sequence satisfies this need and overcomes the deficiencies in the art by utilizing, in accordance with our broad inventive teachings, two different arrays, with each array having illustratively 256 32-bit elements. One array, the S array, contains a 256 element 32-bit S-box. An output stream generated by the S-box, i.e., St, is applied as one input to a first predefined function, e.g., a first hash function. This predefined function, in response to this input, St, multiplied by a variable, C, provides the output pseudo-random sequence, e.g., the keystream. The S-box element St is then updated through a second predefined function, e.g., another hash function, having, as its input, the current value of St multiplied by the variable C. The variable, C, initially a random variable, is itself updated, for use during a next iteration, through an additive combination, of its current value and a corresponding element in the second array (G), i.e., Gt. Both the S-box and G array can be initialized by, e.g., entirely filling each of these arrays with random 32-bit values.
Our inventive technique advantageously operates on a word level, e.g., 32 bits, rather than on a byte level. As such, this technique is considerably faster than the RC4 keystream generator. Moreover, this technique, when used to generate a keystream for use in a stream cipher, appears to be just as secure as does the conventional RC4 cipher. Consequently, our technique is particularly well suited for use in devices, e.g., consumer and other low-end products, that have limited computational resources and would not be amenable to use of the RC4 cipher.
As a feature of our specific inventive teachings, a further random variable and another hash function can be incorporated into our inventive technique, either separately or together, to further enhance its security, if desired, when used in cryptographic application.